package backtrack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *
 * @author gaolainan
 */
public class WordSearch
{
    public static void main(String[] args)
    {
        int n = 1;
        int max = (int)Math.pow(10, n);
    }

    public boolean exist(char[][] board, String word) {

        // 定义二维数组的边界
        int high = board.length;
        int width = board[0].length;
        // 定义used数组
        boolean[][] used = new boolean[high][width];
        // 开始遍历二维数组的每个值
        for (int i = 0;i < high;i++){
            for (int j = 0;j < width;j++){
                // 遍历每个结点
                boolean flag = check(board, used, i, j, word, 0);
                if (flag){
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 检查当前点的的四个方向是否
     * @param board 传进来的二维矩阵的值
     * @param visited 标记当前结点是否已经访问过了
     * @param i 当前点的横坐标
     * @param j 当前点的纵坐标
     * @param s 传进来的字符串
     * @param k
     * @return
     */
    public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k){
        // 当前点的值 不等于 对应的字符串的字符
        if (board[i][j] != s.charAt(k)){
            return false;
            // 当已经遍历完字符串时
        }else if (k == s.length()-1){
            return true;
        }
        // 表示当前结点已经被访问过了
        visited[i][j] = true;
        // 表示当前节点的四个方向
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        boolean result = false;
        // 向四个方向开始遍历
        for (int[] dir : directions){
            // 上下左右的某个点
            int newI = i + dir[0];
            int newJ = j + dir[1];
            // 判断是否越界
            if (newI >= 0 && newI < board.length && newJ >= 0 && newJ < board[0].length){
                // 判断是否被访问过
                if (!visited[newI][newJ]){
                    // 开始字符串的下一个字符遍历
                    boolean flag = check(board, visited, newI, newJ, s, k+1);
                    if (flag){
                        result = true;
                        break;
                    }
                }
            }
        }
        visited[i][j] = false;
        return result;
    }
}
